#ifndef __TDP2_RC_HPP__
#define __TDP2_RC_HPP__

#include "tdp2.hpp"

// Based on 7-zip range coder
// 2009-05-30 : Igor Pavlov : Public domain
namespace TDP
{
	namespace Compression
	{
		const int NumTopBits_k = 24;
		const UInt32 TopValue_k = (1 << NumTopBits_k);

		namespace RangeCoder
		{
			struct SimpleProbabilityTable
			{
				UInt16 *probabilities;
				UInt32 probTotal;
			};

			template<int _TnumTopBits>
			class TEncoder
			{
				UInt32 _cacheSize;
				UInt8 _cache;
				UInt64 _low;
				UInt32 _range;
				UInt8 _output[5];
				int _outOffset;
				static const UInt32 TopValue_k = (1 << _TnumTopBits);

				void ShiftLow();
			public:

				void Init();
				void Flush();
				void Encode(UInt32 start, UInt32 size, UInt32 total);
				const UInt8 *GetOutput();
				int GetOutputCount();
			};

			template<int _TnumTopBits_k>
			class TDecoder
			{
				UInt32 _range;
				UInt32 _code;
				static const UInt32 TopValue_k = (1 << _TnumTopBits_k);
				int _availableBytes;
				bool _initialized;
				UInt8 _input[5];
				int _inOffset;

				void Normalize();
				UInt8 ReadByte();
			public:
				void Init();
				UInt32 GetThreshold(UInt32 total);		// Returns a value somewhere from start..(start+size-1)
				void Decode(UInt32 start, UInt32 size);	// Processes the actual start and size of a code to get the next probability

				void Fill(const UInt8 *bytes);
				int GetFillCount();
			};
			
			typedef TEncoder<24> Encoder;
			typedef TDecoder<24> Decoder;
		}
	}
}

namespace TDP
{
	namespace Compression
	{
		namespace RangeCoder
		{
			template<int _TnumTopBits>
			inline void TEncoder<_TnumTopBits>::Init()
			{
				_low = 0;
				_range = 0xFFFFFFFF;
				_cacheSize = 1;
				_cache = 0;
				_outOffset = 0;
			}
			
			template<int _TnumTopBits>
			inline void TEncoder<_TnumTopBits>::Flush()
			{
				// Low += 1;
				for(int i = 0; i < 5; i++)
					ShiftLow();
			}
			
			template<int _TnumTopBits>
			inline void TEncoder<_TnumTopBits>::Encode(UInt32 start, UInt32 size, UInt32 total)
			{
				_low += start * (_range /= total);
				_range *= size;
				while(_range < TopValue_k)
				{
					_range <<= 8;
					ShiftLow();
				}
			}
			
			template<int _TnumTopBits>
			inline void TEncoder<_TnumTopBits>::ShiftLow()
			{
				if (static_cast<UInt32>(_low) < static_cast<UInt32>(0xFF000000) || static_cast<int>(_low >> 32) != 0)
				{
					UInt8 temp = _cache;
					do
					{
						_output[_outOffset++] = static_cast<UInt8>(temp + static_cast<UInt8>(_low >> 32));
						temp = 0xFF;
					}
					while(--_cacheSize != 0);
					_cache = static_cast<UInt8>(static_cast<UInt32>(_low) >> 24);
				}
				_cacheSize++;
				_low = static_cast<UInt32>(_low) << 8;
			}

			template<int _TnumTopBits>
			inline const UInt8 *TEncoder<_TnumTopBits>::GetOutput()
			{
				_outOffset = 0;
				return _output;
			}

			template<int _TnumTopBits>
			inline int TEncoder<_TnumTopBits>::GetOutputCount()
			{
				return _outOffset;
			}

			// Decoder
			template<int _TnumTopBits>
			inline void TDecoder<_TnumTopBits>::Normalize()
			{
				while(_range < TopValue_k)
				{
					_code = (_code << 8) | _input[_inOffset++];
					_range <<= 8;
				}
			}
  
			template<int _TnumTopBits>
			inline void TDecoder<_TnumTopBits>::Init()
			{
				_code = 0;
				_range = 0xFFFFFFFF;
				_inOffset = 5;
				_initialized = false;
			}
			
			template<int _TnumTopBits>
			inline UInt32 TDecoder<_TnumTopBits>::GetThreshold(UInt32 total)
			{
				return (_code) / (_range /= total);
			}
			
			template<int _TnumTopBits>
			inline void TDecoder<_TnumTopBits>::Decode(UInt32 start, UInt32 size)
			{
				_code -= start * _range;
				_range *= size;
				Normalize();
			}

			template<int _TnumTopBits>
			inline void TDecoder<_TnumTopBits>::Fill(const UInt8 *bytes)
			{
				if(!_initialized)
				{
					for(int i=0;i<5;i++)
						_code = (_code << 8) | bytes[i];
					_initialized = true;
				}
				else
				{
					if(_inOffset == 0)
						return;
					int outOffset = 0;
					// Shift existing bytes back
					for(int i=_inOffset;i<5;i++)
						_input[outOffset++] = _input[i];
					// Read new bytes
					for(int i=0;i<_inOffset;i++)
						_input[outOffset++] = bytes[i];
					_inOffset = 0;
				}
			}

			template<int _TnumTopBits>
			inline int TDecoder<_TnumTopBits>::GetFillCount()
			{
				return _inOffset;
			}
		}
	}
};

#endif
